home *** CD-ROM | disk | FTP | other *** search
/ BCI NET 2 / BCI NET 2.iso / archives / programming / source / graphicgems4.lha / GemsIV / patch_conv.C < prev    next >
Encoding:
C/C++ Source or Header  |  1995-02-06  |  8.8 KB  |  288 lines
  1. /*
  2.  * C++ code from the article
  3.  * "Converting Rectangular Patches into Bezier Triangles"
  4.  * by Dani Lischinski, danix@graphics.cornell.edu
  5.  * in "Graphics Gems IV", Academic Press, 1994
  6.  */
  7.  
  8. /***************************************************************************
  9.  
  10.   This is C++ code. Given here are class definitions and code for the
  11.   control point (ControlPoint) class, quadratic and quartic Bezier
  12.   triangle classes (BezierTri2 and BezierTri4, respectively), and for the
  13.   bilinear and biquadratic Bezier rectangular patch classes (BezierRect1
  14.   and BezierRect2.)
  15.   The conversion described in the gem takes place in the Convert
  16.   member functions of the BezierRect1 and BezierRect2 classes,
  17.   which each take references to two Bezier triangles (of appropriate
  18.   degree) as an argument.
  19.  
  20.   Note that control points do not have to be (x,y,z) triplets.
  21.   For instance, they can be scalars, RGB triplets, etc., as long as the
  22.   operators +, *, /, and = (assignment) are provided. If you have a
  23.   class that you wish to use instead of the one given in the code, all
  24.   you have to do is to remove the definitions of the ControlPoint class
  25.   and its operators, and insert instead something like:
  26.  
  27.     #include <my_class.h>
  28.     typedef MyClass ControlPoint;
  29.  
  30. ***************************************************************************/
  31.  
  32. #include <stream.h>
  33. #include <stdlib.h>
  34. #include <math.h>
  35.  
  36. #define FRAND() (random()/2147483648.) /* uniform rand# in [0,1) */
  37.  
  38. /************* Control Point Class ****************************************/
  39.  
  40. class ControlPoint {
  41. public:
  42.     ControlPoint()                   { x = 0; y = 0; z = 0; }
  43.     ControlPoint(float a, float b, float c)       { x = a; y = b; z = c; }
  44.     ControlPoint operator+(const ControlPoint&);
  45.     ControlPoint operator-(const ControlPoint&);
  46.     friend ControlPoint operator*(float, const ControlPoint&);
  47.     friend ControlPoint operator/(const ControlPoint&, float);
  48.     friend ostream& operator<<(ostream&, const ControlPoint&);
  49. private:
  50.     float x, y, z;
  51. };
  52.  
  53. inline ControlPoint ControlPoint::operator+(const ControlPoint& p)
  54. {
  55.     return ControlPoint(x + p.x, y + p.y, z + p.z);
  56. }
  57.  
  58. inline ControlPoint ControlPoint::operator-(const ControlPoint& p)
  59. {
  60.     return ControlPoint(x - p.x, y - p.y, z - p.z);
  61. }
  62.  
  63. inline ControlPoint operator*(float c, const ControlPoint& a)
  64. {
  65.     return ControlPoint(c * a.x, c * a.y, c * a.z);
  66. }
  67.  
  68. inline ControlPoint operator/(const ControlPoint& a, float c)
  69. {
  70.     return ControlPoint(a.x / c, a.y / c, a.z / c);
  71. }
  72.  
  73. inline ostream& operator<<(ostream& os, const ControlPoint& p)
  74. {
  75.     return os << '(' << p.x << ',' << p.y << ',' << p.z << ") ";
  76. }
  77.  
  78. /************* Quadratic Bezier Triangle Class ****************************/
  79.  
  80. class BezierTri2 {
  81. private:
  82.     ControlPoint cp[6];
  83. public:
  84.     ControlPoint& b(int, int, int);
  85.     ControlPoint operator()(float, float);
  86. };
  87.  
  88. ControlPoint& BezierTri2::b(int i, int j, int /* k */)
  89. // Returns the (i,j,k) control point.
  90. {
  91.     static int row_start[3] = {0, 3, 5};
  92.     return cp[row_start[j] + i];
  93. }
  94.  
  95. ControlPoint BezierTri2::operator()(float u, float v)
  96. // Evaluates the Bezier triangle at (u,v).
  97. {
  98.     float w = 1 - u - v;
  99.     float u2 = u * u;
  100.     float v2 = v * v;
  101.     float w2 = w * w;
  102.     return (w2*b(0,0,2) + (2*u*w)*b(1,0,1) + u2*b(2,0,0) +
  103.         (2*v*w)*b(0,1,1) + (2*u*v)*b(1,1,0) + v2*b(0,2,0));
  104. }
  105.  
  106. /************* Quartic Bezier Triangle Class ******************************/
  107.  
  108. class BezierTri4 {
  109. private:
  110.     ControlPoint cp[15];
  111. public:
  112.     ControlPoint& b(int, int, int);
  113.     ControlPoint operator()(float, float);
  114. };
  115.  
  116. ControlPoint& BezierTri4::b(int i, int j, int /* k */)
  117. // Returns the (i,j,k) control point.
  118. {
  119.     static int row_start[5] = {0, 5, 9, 12, 14};
  120.     return cp[row_start[j] + i];
  121. }
  122.  
  123. ControlPoint BezierTri4::operator()(float u, float v)
  124. // Evaluates the Bezier triangle at (u,v).
  125. {
  126.     float w = 1 - u - v;
  127.     float u2 = u * u, u3 = u2 * u, u4 = u3 * u;
  128.     float v2 = v * v, v3 = v2 * v, v4 = v3 * v;
  129.     float w2 = w * w, w3 = w2 * w, w4 = w3 * w;
  130.     return (w4*b(0,0,4) + (4*u*w3)*b(1,0,3) + (6*u2*w2)*b(2,0,2) +
  131.         (4*u3*w)*b(3,0,1) + u4*b(4,0,0) + (4*v*w3)*b(0,1,3) +
  132.         (12*u*v*w2)*b(1,1,2) + (12*u2*v*w)*b(2,1,1) + (4*u3*v)*b(3,1,0) +
  133.         (6*v2*w2)*b(0,2,2) + (12*u*v2*w)*b(1,2,1) + (6*u2*v2)*b(2,2,0) +
  134.         (4*v3*w)*b(0,3,1) + (4*u*v3)*b(1,3,0) + v4*b(0,4,0));
  135. }
  136.  
  137. /************* Bilinear Bezier Rectangle Class *****************************/
  138.  
  139. class BezierRect1 {
  140. private:
  141.     ControlPoint cp[2][2];
  142. public:
  143.     ControlPoint& p(int i, int j)    { return cp[i][j]; }
  144.     ControlPoint operator()(float, float);
  145.     void Convert(BezierTri2&, BezierTri2&);
  146. };
  147.  
  148. ControlPoint BezierRect1::operator()(float s, float t)
  149. // Evaluates the Bezier rectangle at (s,t).
  150. {
  151.     float s1 = 1 - s;
  152.  
  153.     return ((1-t) * (s1*p(0,0) + s*p(0,1)) +
  154.         t * (s1*p(1,0) + s*p(1,1)));
  155. }
  156.  
  157. void BezierRect1::Convert(BezierTri2& t1, BezierTri2& t2)
  158. // Converts a bilinear Bezier rectangle into two quadratic Bezier
  159. // triangles t1 and t2, such that the value of the bilinear
  160. // at (s,t) is equal to t1(s,t) if (s + t <= 1), and t2(1-t,1-s)
  161. // otherwise.
  162. {
  163.     // lower left triangle:
  164.     t1.b(0,0,2) = p(0,0);
  165.     t1.b(1,0,1) = 0.5 * (p(0,0) + p(0,1));
  166.     t1.b(2,0,0) = p(0,1);
  167.  
  168.     t1.b(0,1,1) = 0.5 * (p(0,0) + p(1,0));
  169.     t1.b(1,1,0) = 0.5 * (p(0,0) + p(1,1));
  170.  
  171.     t1.b(0,2,0) = p(1,0);
  172.  
  173.     // upper right triangle:
  174.     t2.b(0,0,2) = p(1,1);
  175.     t2.b(1,0,1) = 0.5 * (p(1,1) + p(0,1));
  176.     t2.b(2,0,0) = p(0,1);
  177.  
  178.     t2.b(0,1,1) = 0.5 * (p(1,1) + p(1,0));
  179.     t2.b(1,1,0) = 0.5 * (p(0,0) + p(1,1));
  180.  
  181.     t2.b(0,2,0) = p(1,0);
  182. }
  183.  
  184. /************* Biquadratic Bezier Rectangle Class **************************/
  185.  
  186. class BezierRect2 {
  187. private:
  188.     ControlPoint cp[3][3];
  189. public:
  190.     ControlPoint& p(int i, int j)    { return cp[i][j]; }
  191.     ControlPoint operator()(float, float);
  192.     void Convert(BezierTri4&, BezierTri4&);
  193. };
  194.  
  195. ControlPoint BezierRect2::operator()(float s, float t)
  196. // Evaluates the Bezier rectangle at (s,t).
  197. {
  198.     float s1 = 1 - s, ss1 = 2*s*s1, s2 = s*s, s12 = s1*s1;
  199.     float t1 = 1 - t, tt1 = 2*t*t1, t2 = t*t, t12 = t1*t1;
  200.  
  201.     return (t12 * (s12*p(0,0) + ss1*p(0,1) + s2*p(0,2)) +
  202.         tt1 * (s12*p(1,0) + ss1*p(1,1) + s2*p(1,2)) +
  203.         t2    * (s12*p(2,0) + ss1*p(2,1) + s2*p(2,2)));
  204. }
  205.  
  206. void BezierRect2::Convert(BezierTri4& t1, BezierTri4& t2)
  207. // Converts a biquadratic Bezier rectangle into two quartic Bezier
  208. // triangles t1 and t2, such that the value of the biquadratic
  209. // at (s,t) is equal to t1(s,t) if (s + t <= 1), and t2(1-t,1-s)
  210. // otherwise.
  211. {
  212.     // lower left triangle:
  213.     t1.b(0,0,4) = p(0,0);
  214.     t1.b(1,0,3) = 0.5 * (p(0,0) + p(0,1));
  215.     t1.b(2,0,2) = (p(0,0) + 4 * p(0,1) + p(0,2)) / 6;
  216.     t1.b(3,0,1) = 0.5 * (p(0,1) + p(0,2));
  217.     t1.b(4,0,0) = p(0,2);
  218.  
  219.     t1.b(0,1,3) = 0.5 * (p(0,0) + p(1,0));
  220.     t1.b(1,1,2) = (p(0,0) + p(1,1)) / 3 + (p(0,1) + p(1,0)) / 6;
  221.     t1.b(2,1,1) = (p(0,0) + p(1,2)) / 6 + (p(0,1) + p(1,1)) / 3;
  222.     t1.b(3,1,0) = 0.5 * (p(0,1) + p(1,2));
  223.  
  224.     t1.b(0,2,2) = (p(0,0) + 4 * p(1,0) + p(2,0)) / 6;
  225.     t1.b(1,2,1) = (p(0,0) + p(2,1)) / 6 + (p(1,0) + p(1,1)) / 3;
  226.     t1.b(2,2,0) = (p(0,0) + 4 * p(1,1) + p(2,2)) / 6;
  227.  
  228.     t1.b(0,3,1) = 0.5 * (p(1,0) + p(2,0));
  229.     t1.b(1,3,0) = 0.5 * (p(1,0) + p(2,1));
  230.  
  231.     t1.b(0,4,0) = p(2,0);
  232.  
  233.     // upper right triangle:
  234.     t2.b(0,0,4) = p(2,2);
  235.     t2.b(1,0,3) = 0.5 * (p(2,2) + p(1,2));
  236.     t2.b(2,0,2) = (p(2,2) + 4 * p(1,2) + p(0,2)) / 6;
  237.     t2.b(3,0,1) = 0.5 * (p(1,2) + p(0,2));
  238.     t2.b(4,0,0) = p(0,2);
  239.  
  240.     t2.b(0,1,3) = 0.5 * (p(2,2) + p(2,1));
  241.     t2.b(1,1,2) = (p(2,2) + p(1,1)) / 3 + (p(1,2) + p(2,1)) / 6;
  242.     t2.b(2,1,1) = (p(2,2) + p(0,1)) / 6 + (p(1,2) + p(1,1)) / 3;
  243.     t2.b(3,1,0) = 0.5 * (p(0,1) + p(1,2));
  244.  
  245.     t2.b(0,2,2) = (p(2,2) + 4 * p(2,1) + p(2,0)) / 6;
  246.     t2.b(1,2,1) = (p(2,2) + p(1,0)) / 6 + (p(2,1) + p(1,1)) / 3;
  247.     t2.b(2,2,0) = (p(2,2) + 4 * p(1,1) + p(0,0)) / 6;
  248.  
  249.     t2.b(0,3,1) = 0.5 * (p(2,1) + p(2,0));
  250.     t2.b(1,3,0) = 0.5 * (p(1,0) + p(2,1));
  251.  
  252.     t2.b(0,4,0) = p(2,0);
  253. }
  254.  
  255. /************ A Test Program **********************************************/
  256.  
  257. void main()
  258. {
  259.     // init biquadratic Bezier rectangle:
  260.     BezierRect2 brect;
  261.     brect.p(0,0) = ControlPoint(FRAND(), FRAND(), FRAND());
  262.     brect.p(0,1) = ControlPoint(FRAND(), FRAND(), FRAND());
  263.     brect.p(0,2) = ControlPoint(FRAND(), FRAND(), FRAND());
  264.     brect.p(1,0) = ControlPoint(FRAND(), FRAND(), FRAND());
  265.     brect.p(1,1) = ControlPoint(FRAND(), FRAND(), FRAND());
  266.     brect.p(1,2) = ControlPoint(FRAND(), FRAND(), FRAND());
  267.     brect.p(2,0) = ControlPoint(FRAND(), FRAND(), FRAND());
  268.     brect.p(2,1) = ControlPoint(FRAND(), FRAND(), FRAND());
  269.     brect.p(2,2) = ControlPoint(FRAND(), FRAND(), FRAND());
  270.  
  271.     // convert to two quartic Bezier triangles:
  272.     BezierTri4 btri1, btri2;
  273.     brect.Convert(btri1, btri2);
  274.  
  275.     float s, t;
  276.     ControlPoint pt1, pt2;
  277.  
  278.     while (cin >> s >> t) {
  279.     pt1 = brect(s, t);
  280.     if (s + t <= 1.0) {
  281.         pt2 = btri1(s, t);
  282.     } else {
  283.         pt2 = btri2(1-t, 1-s);
  284.     }
  285.     cerr << pt1 - pt2 << endl;
  286.     }
  287. }
  288.